package 剑指Offer;

public class Offer13_机器人的运动范围 {
    int rows;
    int cols;
    boolean[][] visited;

    //求数位和的方法
    public int help(int num) {
        int s = 0;
        while (num != 0) {
            s = s + num % 10;
            num = num / 10;
        }
        return s;
    }

    public int movingCount(int m, int n, int k) {
        this.rows = m;
        this.cols = n;
        this.visited = new boolean[m][n];
        return dfs(0, 0, k);
    }

    //i,j：开始的坐标
    public int dfs(int i, int j, int k) {
        if (i >= rows || j >= cols || (help(i) + help(j)) > k || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;

//返回 1 + 下方搜索的可达解总数 + 右方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。
        return 1 + dfs(i + 1, j, k) + dfs(i, j + 1, k);
    }
}
